package sliding_window

/*
给你一个整数数组 nums 和两个整数k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。
如果存在则返回 true，不存在返回 false。

示例1：
输入：nums = [1,2,3,1], k = 3, t = 0
输出：true

示例 2：
输入：nums = [1,0,1,1], k = 1, t = 2
输出：true

示例 3：
输入：nums = [1,5,9,1,5,9], k = 2, t = 3
输出：false

*/

//我们也可以使用利用桶排序的思想解决本题。我们按照元素的大小进行分桶，维护一个滑动窗口内的元素对应的元素。
//对于元素 x，其影响的区间为 [x−t,x+t]。于是我们可以设定桶的大小为 t+1。如果两个元素同属一个桶，那么这两个元素必然符合条件。如果两个元素属于相邻桶，那么我们需要校验这两个元素是否差值不超过 t。
//如果两个元素既不属于同一个桶，也不属于相邻桶，那么这两个元素必然不符合条件。
//具体地，我们遍历该序列，假设当前遍历到元素 x，那么我们首先检查 x所属于的桶是否已经存在元素，如果存在，那么我们就找到了一对符合条件的元素，否则我们继续检查两个相邻的桶内是否存在符合条件的元素。
//
//实现方面，我们将 int 范围内的每一个整数 x 表示为x=(t+1)×a+b(0≤b≤t) （b 指的是相邻的桶）的形式，这样 x 即归属于编号为 a 的桶。因为一个桶内至多只会有一个元素，所以我们使用哈希表实现即可。
//时间复杂度：O(n)，其中 n 是给定数组的长度。每个元素至多被插入哈希表和从哈希表中删除一次，每次操作的时间复杂度均为 O(1)。
//空间复杂度：O(min(n,k))，其中 n 是给定数组的长度。哈希表中至多包含 min(n,k+1) 个元素。
func containsNearbyAlmostDuplicateBucket(nums []int, k int, t int) bool {
	mp := map[int]int{}
	for i, x := range nums {
		id := getID(x, t+1)
		if _, has := mp[id]; has {
			return true
		}
		// 比较值的差值
		if y, has := mp[id-1]; has && abs(x-y) <= t {
			return true
		}

		if y, has := mp[id+1]; has && abs(x-y) <= t {
			return true
		}
		//放入桶中
		mp[id] = x
		//设置窗口大小
		if i >= k {
			delete(mp, getID(nums[i-k], t+1)) //每个元素至多被插入哈希表和从哈希表中删除一次
		}
	}
	return false
}

//将每一个整数x表示为x=(t+1)*a+b(0<=b<=t),这样x即归属于编号为a的桶
//w 为桶的大小
func getID(x, w int) int {
	if x >= 0 {
		return x / w
	}
	return (x+1)/w - 1
}
